package com.dy.排序.内排序.选择排序.堆排序;

import java.util.Arrays;
/*
O(nlogn)，不稳定
 */

/**
 * 先构建小顶堆，从中间往前构造
 * 然后将堆顶和末尾交换，从头调整为小顶堆，循环
 */
public class HeadSort {
    public static void heapSort(int[] nums){
        //首先构建小顶堆，从后往前构造
        int len = nums.length;
        for(int i =(len-1)/2;i>=0;i--){
            sift(nums,i,len-1);
        }

        //之后将堆顶和末尾交换，再次调整
        for(int i=len-1;i>0;i--){
            int tmp = nums[i];
            nums[i] = nums[0];
            nums[0] = tmp;
            sift(nums,0,i-1);
        }


    }
    //将以low为根节点的子树调整为小顶堆,low和high都是index
    public static  void sift(int[] nums,int low, int high){
        int i =low;
        int j = 2*i+1;//左孩子
        int tmp = nums[i];
        while(j<=high){
            //寻找左孩子和右孩子中的小值，赋给J
            if(j<=high-1 && nums[j]>nums[j+1]) j++;
            if(nums[j]<tmp){
                nums[i] = nums[j];
                i=j;
                j=2*i+1;
            }
            //当比根节点大时退出循环
            else{
                j=high+1;
            }
        }
        //将nums[i]赋为之前的大值
        nums[i] = tmp;
    }
/*
                3
              2    4
            1   0
 */
    public static void main(String[] args) {
        int nums[] = {3,1,7,2,8,99,3,1};
        //sift(nums,0,4);
        heapSort(nums);
        Arrays.stream(nums).forEach(System.out::println);
    }
}
